<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>框架套路解算法 | Cquang博客</title><meta name="keywords" content="算法,算法框架套路"><meta name="author" content="Cai XianQuan"><meta name="copyright" content="Cai XianQuan"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><meta name="description" content="学习《labuladong的算法小抄》，总结积累，方便温习学习">
<meta property="og:type" content="article">
<meta property="og:title" content="框架套路解算法">
<meta property="og:url" content="https://xquan123.gitee.io/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/index.html">
<meta property="og:site_name" content="Cquang博客">
<meta property="og:description" content="学习《labuladong的算法小抄》，总结积累，方便温习学习">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://xquan123.gitee.io/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95%E9%A6%96%E9%A1%B5.jpg">
<meta property="article:published_time" content="2021-01-29T07:37:55.000Z">
<meta property="article:modified_time" content="2021-02-02T03:45:10.788Z">
<meta property="article:author" content="Cai XianQuan">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="算法框架套路">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://xquan123.gitee.io/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95%E9%A6%96%E9%A1%B5.jpg"><link rel="shortcut icon" href="/blog/img/favicon1.png"><link rel="canonical" href="https://xquan123.gitee.io/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//fonts.googleapis.com" crossorigin="crossorigin"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/blog/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Titillium+Web"><script>var GLOBAL_CONFIG = { 
  root: '/blog/',
  algolia: undefined,
  localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"簡"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  ClickShowText: undefined,
  lightbox: 'mediumZoom',
  Snackbar: {"chs_to_cht":"你已切换为繁体","cht_to_chs":"你已切换为简体","day_to_night":"你已切换为深色模式","night_to_day":"你已切换为浅色模式","bgLight":"#49b1f5","bgDark":"#121212","position":"bottom-left"},
  justifiedGallery: {
    js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
    css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
  },
  isPhotoFigcaption: true,
  islazyload: false,
  isanchor: false
};

var saveToLocal = {
  set: function setWithExpiry(key, value, ttl) {
    const now = new Date()
    const expiryDay = ttl * 86400000
    const item = {
      value: value,
      expiry: now.getTime() + expiryDay,
    }
    localStorage.setItem(key, JSON.stringify(item))
  },

  get: function getWithExpiry(key) {
    const itemStr = localStorage.getItem(key)

    if (!itemStr) {
      return undefined
    }
    const item = JSON.parse(itemStr)
    const now = new Date()

    if (now.getTime() > item.expiry) {
      localStorage.removeItem(key)
      return undefined
    }
    return item.value
  }
}</script><script id="config_change">var GLOBAL_CONFIG_SITE = { 
  isPost: true,
  isHome: false,
  isHighlightShrink: true,
  isToc: true,
  postUpdate: '2021-02-02 11:45:10'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(function () {  window.activateDarkMode = function () {
    document.documentElement.setAttribute('data-theme', 'dark')
    if (document.querySelector('meta[name="theme-color"]') !== null) {
      document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
    }
  }
  window.activateLightMode = function () {
    document.documentElement.setAttribute('data-theme', 'light')
   if (document.querySelector('meta[name="theme-color"]') !== null) {
      document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
    }
  }
  const autoChangeMode = 'false'
  const t = saveToLocal.get('theme')
  if (autoChangeMode === '1') {
    const isDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches
    const isLightMode = window.matchMedia('(prefers-color-scheme: light)').matches
    const isNotSpecified = window.matchMedia('(prefers-color-scheme: no-preference)').matches
    const hasNoSupport = !isDarkMode && !isLightMode && !isNotSpecified
    if (t === undefined) {
      if (isLightMode) activateLightMode()
      else if (isDarkMode) activateDarkMode()
      else if (isNotSpecified || hasNoSupport) {
        const now = new Date()
        const hour = now.getHours()
        const isNight = hour <= 6 || hour >= 18
        isNight ? activateDarkMode() : activateLightMode()
      }
      window.matchMedia('(prefers-color-scheme: dark)').addListener(function (e) {
        if (saveToLocal.get('theme') === undefined) {
          e.matches ? activateDarkMode() : activateLightMode()
        }
      })
    } else if (t === 'light') activateLightMode()
    else activateDarkMode()
  } else if (autoChangeMode === '2') {
    const now = new Date()
    const hour = now.getHours()
    const isNight = hour <= 6 || hour >= 18
    if (t === undefined) isNight ? activateDarkMode() : activateLightMode()
    else if (t === 'light') activateLightMode()
    else activateDarkMode()
  } else {
    if (t === 'dark') activateDarkMode()
    else if (t === 'light') activateLightMode()
  }const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
   if (asideStatus === 'hide') {
     document.documentElement.classList.add('hide-aside')
   } else {
     document.documentElement.classList.remove('hide-aside')
   }
}})()</script><link rel="stylesheet" href="/css/VolantisTags.css"><meta name="generator" content="Hexo 5.3.0"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="author-avatar"><img class="avatar-img" src="/blog/img/%E5%A4%B4%E5%83%8F.gif" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/blog/archives/"><div class="headline">文章</div><div class="length-num">22</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/blog/tags/"><div class="headline">标签</div><div class="length-num">33</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/blog/categories/"><div class="headline">分类</div><div class="length-num">18</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/blog/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/blog/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/blog/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/blog/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 享受时光</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/blog/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li></ul></div></div></div></div><div id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url(/blog/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95%E9%A6%96%E9%A1%B5.jpg)"><nav id="nav"><span id="blog_name"><a id="site-name" href="/blog/">Cquang博客</a></span><span id="menus"><div id="search_button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/blog/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/blog/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/blog/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/blog/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 享受时光</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/blog/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li></ul></div></div><span class="close" id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></span></span></nav><div id="post-info"><h1 class="post-title">框架套路解算法</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-01-29T07:37:55.000Z" title="发表于 2021-01-29 15:37:55">2021-01-29</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-02-02T03:45:10.788Z" title="更新于 2021-02-02 11:45:10">2021-02-02</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/blog/categories/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0/">算法学习</a></span></div><div class="meta-secondline"> <span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">4.3k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>13分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><div class="note info flat"><figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line">--头部属性说明：</span><br><span class="line">title	【必需】文章标题【需要】</span><br><span class="line">date	【必需】文章创建日期【需要】</span><br><span class="line">tags	【可选】文章标签【需要】</span><br><span class="line">categories	【可选】文章分类【需要】</span><br><span class="line">keywords	【可选】文章关键字【需要，同标签】</span><br><span class="line">description	【可选】文章描述【需要】</span><br><span class="line">top_img	【可选】文章顶部图片</span><br><span class="line">cover	【可选】文章缩略图(如果没有设置top_img,文章页顶部将显示缩略图，可设为false/图片地址/留空)【需要，地址为：/年/月/日/文章生成的文件夹名/图片名称.后缀名】</span><br><span class="line">comments	【可选】显示文章评论模块(默认 true)</span><br><span class="line">toc	【可选】显示文章TOC(默认为设置中toc的enable配置)</span><br><span class="line">toc_number	【可选】显示</span><br><span class="line">toc_number	(默认为设置中toc的number配置)</span><br><span class="line">copyright	【可选】显示文章版权模块(默认 true)</span><br><span class="line">mathjax	【可选】显示mathjax(当设置mathjax的per_page: false时，才需要配置，默认 false)</span><br><span class="line">katex	【可选】显示katex(当设置katex的per_page: false时，才需要配置，默认 false)</span><br><span class="line"></span><br><span class="line">--标签外挂</span><br><span class="line">样式：</span><br><span class="line">[class] : default | primary | success | info | warning | danger.</span><br><span class="line">&#123;% note info %&#125;</span><br><span class="line">编辑内容</span><br><span class="line">&#123;% endnote %&#125;</span><br><span class="line"></span><br><span class="line">--图片插入示例：</span><br><span class="line">不显示描述，可以插入【舍弃不用】：</span><br><span class="line">&#123;% asset_img example.png %&#125;</span><br><span class="line">显示描述的：</span><br><span class="line">![example](example.png)	不用添加路径，直接填图片名称即可，将图片放入对应文件夹内</span><br><span class="line"></span><br><span class="line">-- 插入链接</span><br><span class="line">&#123;% link text url [external] [title] %&#125;</span><br><span class="line"></span><br><span class="line">--</span><br><span class="line">参考地址：[git 无法添加文件夹下文件](https://www.cnblogs.com/howdop/p/5583342.html)</span><br></pre></td></tr></table></figure></div>

<h1 id="开篇词"><a href="#开篇词" class="headerlink" title="开篇词"></a>开篇词</h1><h2 id="目标"><a href="#目标" class="headerlink" title="目标"></a>目标</h2><ol>
<li><p><font color=red size=3><strong><em>可以量化的才叫目标</em></strong></font></p>
<div class="note primary flat"><p>比如说目标是进大厂，计划半年内刷 300 道题，那这可以反向拆分，每个月刷 50 道，工作日每天刷两道，休息日每天刷一道，再细化，每天几点到几点固定为刷题时间，期间屏蔽所有应用通知，专心做题思考；然后每天反省刷题计划是否达标，如果没达标，是为什么，怎么弥补。</p>
<p>这就是计算机的递归思维，自顶向下，逐步求精，反向求解。我们旧文写了很多动态规划相关的题目，基本都是先写自顶向下的递归解法，然后改写成自底向上的迭代解法，因为递归思路清晰嘛。</p>
<p><font color=blue size=3><strong><em>制定一个计划，而且必须有非常强的坚定意志以及耐心，能够扛得住诱惑经得起枯燥。。。</em></strong></font></p>
</div>
</li>
<li><p>两点：目标和明白</p>
</li>
</ol>
<p>以下摘抄自算法小抄：<br>不是说今天热血沸腾给自己制定计划，结果做着做着就被带偏了，真的明白应该是你每时每刻，每分每秒都明白目标是什么。<br>我指的被带偏不是说学着学着跑去刷抖音了，这种问题可以通过物理隔离等方法避免，我说的带偏是指方向跑偏。<br>比如说做英语阅读理解，见到一个不认识的词，就去查，这个过程中又见到十个不认识的词，然后又去查，结果一个小时过去了，查了不少单词，但是文章没读几句，题还没做。<br>你说他没学习，倒也认真学了，但是学着学着方向跑偏了，最后挂科了。<br>这就是没搞明白目标是啥，这种 DFS 查单词的事情，应该是背单词的时候去做，现在做阅读题呢，目标是快速理解文章内容，选出正确答案嘛。那么几个生僻词汇，影响你对全文内容的掌握吗？<br>说回学算法，每个人的自身处境不同，需求不同，就应该有不同的学习策略，就像背单词和做阅读两个场景采取两种策略一样。<br>经常有读者后台留言，让我写一些特别硬核特别难的内容，我都婉言拒绝了；还有的大佬抨击我把算法写成模板是在害人，我也就笑笑不说话。<br>因为我就很明白咱们讲的这些算法到底是个什么定位，无非就是个锻炼思维能力，准备笔试面试的工具。<br>需要笔试了，欢迎你来突击学习一下；不需要笔试的话，每天早上地铁上看看，做做思维早操，一天精神好，仅此而已。<br>大部分读者需要的就是这些，我们号的定位也就是这样。好比初高中的广播体操，就是让学生伸伸胳膊踢踢腿，有益身心健康；你非要说练习后空翻才叫体操，让学生课间练空翻，那估计得出人命了。<br>从个人的角度，学算法，也要时时刻刻「明白」自己想要的是啥。<br>如果目标就是从事算法相关的理论研究工作，去啃《算法导论》这种理论性很强的教材完全没问题，反正你还要在学术的路上走很多年，花上一两年打基础性价比挺高。<br>如果目标是找工作赚钱，那算法就起到个筛选作用，没必要啃大部头，我们号的风格就是你需要的。从各种算法的模板练起，配合历史文章边看边刷，总共可以刷掉将近两百题，国内大厂过算法关没什么问题。节约下来的时间，干点别的不香吗？<br>说实话我个人更倾向于后者，向钱看齐，那么算法只是个工具。有很多读者纠结于要不要打个竞赛刷个公开课之类的，我觉得大可不必，就好比你跑步，朝着终点直线冲刺最划算，非要跑 S 型秀个蛇皮走位，何苦呢？<br>人的精力真的是有限的，把每分每秒都压在刀刃上，才能更快达成目标不是么。<br>当然，不论选择什么，定好目标后都要仔细拆分，严格执行，这个就看个人的执行力了。<br>本文写了些方法论层面的东西，主要希望大家搞清楚自己学习的目标，制定自己的计划，有自己的思考。不要被乱七八糟的建议牵着鼻子走，今天查一个单词，明天查一个单词，结果到头来挂科了。</p>
<h1 id="学习算法和刷题的框架思维"><a href="#学习算法和刷题的框架思维" class="headerlink" title="学习算法和刷题的框架思维"></a>学习算法和刷题的框架思维</h1><h2 id="数据结构的存储方式"><a href="#数据结构的存储方式" class="headerlink" title="数据结构的存储方式"></a>数据结构的存储方式</h2><ol>
<li><p><font color=black size=3><strong><em>数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改</em></strong></font>。最基本的两种存储方式是数组和链表。</p>
</li>
<li><p><font color=red size=3><strong><em>数组</em></strong></font>：由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。</p>
</li>
<li><p><font color=red size=3><strong><em>链表</em></strong></font>：因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。</p>
</li>
</ol>
<h2 id="算法刷题指南"><a href="#算法刷题指南" class="headerlink" title="算法刷题指南"></a>算法刷题指南</h2><ol>
<li><font color=black size=3><strong><em>先刷二叉树</em></strong></font>：因为二叉树是最容易培养框架思维的，而且大部分算法技巧，本质上都是树的遍历问题。<ul>
<li>对于一个理解二叉树的人来说，刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手，前 10 道也许有点难受；结合框架再做 20 道，也许你就有点自己的理解了；刷完整个专题，再去做什么回溯动规分治专题，你就会发现<font color=red size=3><strong><em>只要涉及递归的问题，都是树的问题</em></strong></font>。</li>
</ul>
</li>
</ol>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><ol>
<li>数据结构的基本存储方式就是链式和顺序两种，基本操作就是增删查改，遍历方式无非迭代和递归。</li>
<li>刷算法题建议从「树」分类开始刷，结合框架思维，把这几十道题刷完，对于树结构的理解应该就到位了。这时候去看回溯、动规、分治等算法专题，对思路的理解可能会更加深刻一些。</li>
</ol>
<h2 id="推荐书籍"><a href="#推荐书籍" class="headerlink" title="推荐书籍"></a>推荐书籍</h2><ol>
<li>算法 第4版</li>
</ol>
<h1 id="通用解题套路框架"><a href="#通用解题套路框架" class="headerlink" title="通用解题套路框架"></a>通用解题套路框架</h1><h2 id="动态规划解题套路框架"><a href="#动态规划解题套路框架" class="headerlink" title="动态规划解题套路框架"></a>动态规划解题套路框架</h2><h3 id="知识储备"><a href="#知识储备" class="headerlink" title="知识储备"></a>知识储备</h3><ol>
<li>动态规划问题的一般形式是求最值，列出<code>状态转移方程</code></li>
<li>求解动态规划的核心问题是穷举，一定会具备<code>最优子结构</code></li>
<li><code>存在重叠子问题</code>: 使用“备忘录”或“DP table”</li>
<li>三要素：重叠子问题，最优子结构，状态转移方程</li>
</ol>
<h3 id="套路框架"><a href="#套路框架" class="headerlink" title="套路框架"></a>套路框架</h3><ol>
<li><p>思维框架：</p>
<figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">明确 base case -&gt; 明确「状态」-&gt; 明确「选择」 -&gt; 定义 dp 数组/函数的含义。</span><br></pre></td></tr></table></figure></li>
<li><p>通用框架代码</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"># 初始化 base case</span><br><span class="line">dp[<span class="number">0</span>][<span class="number">0</span>][...] = base</span><br><span class="line"># 进行状态转移</span><br><span class="line"><span class="keyword">for</span> 状态<span class="number">1</span> in 状态<span class="number">1</span>的所有取值：</span><br><span class="line">    <span class="keyword">for</span> 状态<span class="number">2</span> in 状态<span class="number">2</span>的所有取值：</span><br><span class="line">        <span class="keyword">for</span> ...</span><br><span class="line">            dp[状态<span class="number">1</span>][状态<span class="number">2</span>][...] = 求最值(选择<span class="number">1</span>，选择<span class="number">2.</span>..)</span><br></pre></td></tr></table></figure>
<h3 id="举例说明"><a href="#举例说明" class="headerlink" title="举例说明"></a>举例说明</h3><h4 id="斐波那契数列"><a href="#斐波那契数列" class="headerlink" title="斐波那契数列"></a>斐波那契数列</h4></li>
<li><p>暴力递归</p>
<ul>
<li><code>递归算法的时间复杂度等于用子问题个数乘以解决一个子问题需要的时间。</code><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">fib</span><span class="params">(<span class="keyword">int</span> N)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (N == <span class="number">1</span> || N == <span class="number">2</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> fib(N - <span class="number">1</span>) + fib(N - <span class="number">2</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<img src="1%E3%80%81%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97%E9%80%92%E5%BD%92%E7%A4%BA%E6%84%8F%E5%9B%BE.png" alt="斐波那契数列递归示意图"><div class="note primary flat"><p><font color=red size=3><strong><em>但凡遇到需要递归的问题，最好都画出递归树，对分析算法的复杂度，寻找算法低效的原因都有巨大帮助。</em></strong></font></p>
</div></li>
<li>可以发现，出现重复计算问题，即重叠子问题</li>
</ul>
</li>
<li><p>带备忘录的递归解法</p>
<ul>
<li>一般使用一个数组充当这个「备忘录」，可以使用哈希表（字典），思想都是一样的。<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">fib</span><span class="params">(<span class="keyword">int</span> N)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (N &lt; <span class="number">1</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 备忘录全初始化为 0</span></span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">memo</span><span class="params">(N + <span class="number">1</span>, <span class="number">0</span>)</span></span>;</span><br><span class="line">    <span class="comment">// 进行带备忘录的递归</span></span><br><span class="line">    <span class="keyword">return</span> helper(memo, N);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">helper</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt;&amp; memo, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// base case</span></span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">1</span> || n == <span class="number">2</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="comment">// 已经计算过</span></span><br><span class="line">    <span class="keyword">if</span> (memo[n] != <span class="number">0</span>) <span class="keyword">return</span> memo[n];</span><br><span class="line">    memo[n] = helper(memo, n - <span class="number">1</span>) + helper(memo, n - <span class="number">2</span>);</span><br><span class="line">    <span class="keyword">return</span> memo[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<img src="2%E3%80%81%E4%BD%BF%E7%94%A8%E5%A4%87%E5%BF%98%E5%BD%95%E8%A7%A3%E5%86%B3%E9%87%8D%E5%8F%A0%E5%AD%90%E9%97%AE%E9%A2%98.png" alt="使用备忘录解决重叠子问题"><br><img src="3%E3%80%81%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B%E6%B1%82%E8%A7%A3%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97.png" alt="自顶向下求解斐波那契数列"></li>
<li>子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。</li>
<li>带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。</li>
</ul>
</li>
<li><p>dp 数组的迭代解法</p>
<ul>
<li>将备忘录可以进一步独立为一张表：DP table,从而实现自底向上<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">fib</span><span class="params">(<span class="keyword">int</span> N)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (N &lt; <span class="number">1</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span> (N == <span class="number">1</span> || N == <span class="number">2</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">dp</span><span class="params">(N + <span class="number">1</span>, <span class="number">0</span>)</span></span>;</span><br><span class="line">    <span class="comment">// base case</span></span><br><span class="line">    dp[<span class="number">1</span>] = dp[<span class="number">2</span>] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">3</span>; i &lt;= N; i++)</span><br><span class="line">        dp[i] = dp[i - <span class="number">1</span>] + dp[i - <span class="number">2</span>];</span><br><span class="line">    <span class="keyword">return</span> dp[N];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<img src="4%E3%80%81DPTable%E6%B1%82%E8%A7%A3.png" alt="DPTable求解"></li>
</ul>
</li>
</ol>
<h5 id="状态转移方程"><a href="#状态转移方程" class="headerlink" title="状态转移方程"></a>状态转移方程</h5><ol>
<li><p>描述问题结构的数学形式：<br><img src="5%E3%80%81%E8%BD%AC%E7%A7%BB%E7%8A%B6%E6%80%81%E6%96%B9%E7%A8%8B%E9%80%9A%E7%94%A8%E5%85%AC%E5%BC%8F.png" alt="转移状态方程通用公式"></p>
<ul>
<li>把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移</li>
</ul>
</li>
<li><p>上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法。<br><font color=red size=3><strong><em>千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。</em></strong></font>只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。</p>
</li>
</ol>
<h5 id="斐波那契数列细节优化"><a href="#斐波那契数列细节优化" class="headerlink" title="斐波那契数列细节优化"></a>斐波那契数列细节优化</h5><ul>
<li>根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">fib</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n &lt; <span class="number">1</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">2</span> || n == <span class="number">1</span>) </span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> prev = <span class="number">1</span>, curr = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">3</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> sum = prev + curr;</span><br><span class="line">        prev = curr;</span><br><span class="line">        curr = sum;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> curr;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
<li>以上优化的技巧叫<code>状态压缩</code>。如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。后续的动态规划章节中我们还会看到这样的例子，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从 O(n^2) 压缩到 O(n)。</li>
</ul>
<h4 id="凑零钱问题"><a href="#凑零钱问题" class="headerlink" title="凑零钱问题"></a>凑零钱问题</h4><ol>
<li><p>题目<br>给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// coins 中是可选硬币面值，amount 是目标金额</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">coinChange</span><span class="params">(<span class="keyword">int</span>[] coins, <span class="keyword">int</span> amount)</span></span>;</span><br></pre></td></tr></table></figure>
<p>比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。</p>
</li>
<li><p>暴力递归</p>
<ul>
<li>这个问题是动态规划问题，因为它具有「最优子结构」的。<code>要符合「最优子结构」，子问题间必须互相独立</code>。</li>
<li>什么是相互独立：假设你考试，每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。<br>得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。</li>
<li><font color=red size=3><strong><em>如何列出正确的状态转移方程</em></strong></font>？<ul>
<li><code>确定 base case</code>，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。</li>
<li><code>确定「状态」，也就是原问题和子问题中会变化的变量。</code>由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。</li>
<li><code>确定「选择」，也就是导致「状态」产生变化的行为。</code>目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。</li>
<li><code>明确 dp 函数/数组的定义。</code>我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：<br>dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。<br>搞清楚上面这几个关键点，解法的伪码就可以写出来了：</li>
</ul>
</li>
</ul>
</li>
</ol>
<p><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"><br><img src="example.png" alt="example"></p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">Cai XianQuan</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://xquan123.gitee.io/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/">https://xquan123.gitee.io/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://xquan123.gitee.io" target="_blank">Cquang博客</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/blog/tags/%E7%AE%97%E6%B3%95/">算法</a><a class="post-meta__tags" href="/blog/tags/%E7%AE%97%E6%B3%95%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF/">算法框架套路</a></div><div class="post_share"><div class="social-share" data-image="/blog/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95%E9%A6%96%E9%A1%B5.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="next-post pull-full"><a href="/blog/2021/01/07/shell%E8%84%9A%E6%9C%AC%E5%AD%A6%E4%B9%A0/"><img class="next-cover" src="/blog/2021/01/07/shell%E8%84%9A%E6%9C%AC%E5%AD%A6%E4%B9%A0/shell%E8%84%9A%E6%9C%AC%E5%AD%A6%E4%B9%A0%E9%A6%96%E9%A1%B5.jpg" onerror="onerror=null;src='/blog/img/404.jpg'"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">shell脚本学习</div></div></a></div></nav></div><div class="aside_content" id="aside_content"><div class="card-widget card-info"><div class="card-content"><div class="card-info-avatar is-center"><img class="avatar-img" src="/blog/img/%E5%A4%B4%E5%83%8F.gif" onerror="this.onerror=null;this.src='/blog/img/friend_404.gif'" alt="avatar"/><div class="author-info__name">Cai XianQuan</div><div class="author-info__description"></div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/blog/archives/"><div class="headline">文章</div><div class="length-num">22</div></a></div><div class="card-info-data-item is-center"><a href="/blog/tags/"><div class="headline">标签</div><div class="length-num">33</div></a></div><div class="card-info-data-item is-center"><a href="/blog/categories/"><div class="headline">分类</div><div class="length-num">18</div></a></div></div><a class="button--animated" id="card-info-btn" href="javascript:;"><i class="fab fa-bookmark"></i><span>加入书签</span></a></div></div><div class="card-widget card-announcement"><div class="card-content"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">一花一世界,一木一菩提╮(￣▽ ￣)╭</div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="card-content"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%BC%80%E7%AF%87%E8%AF%8D"><span class="toc-number">1.</span> <span class="toc-text">开篇词</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%9B%AE%E6%A0%87"><span class="toc-number">1.1.</span> <span class="toc-text">目标</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%AD%A6%E4%B9%A0%E7%AE%97%E6%B3%95%E5%92%8C%E5%88%B7%E9%A2%98%E7%9A%84%E6%A1%86%E6%9E%B6%E6%80%9D%E7%BB%B4"><span class="toc-number">2.</span> <span class="toc-text">学习算法和刷题的框架思维</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F"><span class="toc-number">2.1.</span> <span class="toc-text">数据结构的存储方式</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98%E6%8C%87%E5%8D%97"><span class="toc-number">2.2.</span> <span class="toc-text">算法刷题指南</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-number">2.3.</span> <span class="toc-text">总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8E%A8%E8%8D%90%E4%B9%A6%E7%B1%8D"><span class="toc-number">2.4.</span> <span class="toc-text">推荐书籍</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E9%80%9A%E7%94%A8%E8%A7%A3%E9%A2%98%E5%A5%97%E8%B7%AF%E6%A1%86%E6%9E%B6"><span class="toc-number">3.</span> <span class="toc-text">通用解题套路框架</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E8%A7%A3%E9%A2%98%E5%A5%97%E8%B7%AF%E6%A1%86%E6%9E%B6"><span class="toc-number">3.1.</span> <span class="toc-text">动态规划解题套路框架</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%9F%A5%E8%AF%86%E5%82%A8%E5%A4%87"><span class="toc-number">3.1.1.</span> <span class="toc-text">知识储备</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%A5%97%E8%B7%AF%E6%A1%86%E6%9E%B6"><span class="toc-number">3.1.2.</span> <span class="toc-text">套路框架</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BE%E4%BE%8B%E8%AF%B4%E6%98%8E"><span class="toc-number">3.1.3.</span> <span class="toc-text">举例说明</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97"><span class="toc-number">3.1.3.1.</span> <span class="toc-text">斐波那契数列</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E6%96%B9%E7%A8%8B"><span class="toc-number">3.1.3.1.1.</span> <span class="toc-text">状态转移方程</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97%E7%BB%86%E8%8A%82%E4%BC%98%E5%8C%96"><span class="toc-number">3.1.3.1.2.</span> <span class="toc-text">斐波那契数列细节优化</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%87%91%E9%9B%B6%E9%92%B1%E9%97%AE%E9%A2%98"><span class="toc-number">3.1.3.2.</span> <span class="toc-text">凑零钱问题</span></a></li></ol></li></ol></li></ol></li></ol></div></div></div><div class="card-widget card-recent-post"><div class="card-content"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/blog/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/" title="框架套路解算法"><img src="/blog/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95%E9%A6%96%E9%A1%B5.jpg" onerror="this.onerror=null;this.src='/blog/img/404.jpg'" alt="框架套路解算法"/></a><div class="content"><a class="title" href="/blog/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/" title="框架套路解算法">框架套路解算法</a><time datetime="2021-01-29T07:37:55.000Z" title="发表于 2021-01-29 15:37:55">2021-01-29</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/blog/2021/01/07/shell%E8%84%9A%E6%9C%AC%E5%AD%A6%E4%B9%A0/" title="shell脚本学习"><img src="/blog/2021/01/07/shell%E8%84%9A%E6%9C%AC%E5%AD%A6%E4%B9%A0/shell%E8%84%9A%E6%9C%AC%E5%AD%A6%E4%B9%A0%E9%A6%96%E9%A1%B5.jpg" onerror="this.onerror=null;this.src='/blog/img/404.jpg'" alt="shell脚本学习"/></a><div class="content"><a class="title" href="/blog/2021/01/07/shell%E8%84%9A%E6%9C%AC%E5%AD%A6%E4%B9%A0/" title="shell脚本学习">shell脚本学习</a><time datetime="2021-01-07T03:29:18.000Z" title="发表于 2021-01-07 11:29:18">2021-01-07</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/blog/2020/12/28/Linux%E9%97%AE%E9%A2%98%E9%9B%86%E9%94%A6/" title="Linux问题集锦"><img src="/blog/2020/12/28/Linux%E9%97%AE%E9%A2%98%E9%9B%86%E9%94%A6/Linux%E9%97%AE%E9%A2%98%E9%9B%86%E9%94%A6%E9%A6%96%E9%A1%B5.png" onerror="this.onerror=null;this.src='/blog/img/404.jpg'" alt="Linux问题集锦"/></a><div class="content"><a class="title" href="/blog/2020/12/28/Linux%E9%97%AE%E9%A2%98%E9%9B%86%E9%94%A6/" title="Linux问题集锦">Linux问题集锦</a><time datetime="2020-12-28T01:56:38.000Z" title="发表于 2020-12-28 09:56:38">2020-12-28</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/blog/2020/12/13/%E5%B8%B8%E7%94%A8%E7%9A%84Linux%E5%91%BD%E4%BB%A4%E9%9B%86/" title="常用的Linux命令集"><img src="/blog/2020/12/13/%E5%B8%B8%E7%94%A8%E7%9A%84Linux%E5%91%BD%E4%BB%A4%E9%9B%86/%E5%B8%B8%E7%94%A8%E7%9A%84Linux%E5%91%BD%E4%BB%A4%E9%9B%86%E9%A6%96%E9%A1%B5.jpg" onerror="this.onerror=null;this.src='/blog/img/404.jpg'" alt="常用的Linux命令集"/></a><div class="content"><a class="title" href="/blog/2020/12/13/%E5%B8%B8%E7%94%A8%E7%9A%84Linux%E5%91%BD%E4%BB%A4%E9%9B%86/" title="常用的Linux命令集">常用的Linux命令集</a><time datetime="2020-12-13T14:32:23.000Z" title="发表于 2020-12-13 22:32:23">2020-12-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/blog/2020/12/13/Flink%E5%85%A5%E9%97%A8%E5%AD%A6%E4%B9%A0/" title="Flink入门学习"><img src="/blog/2020/12/13/Flink%E5%85%A5%E9%97%A8%E5%AD%A6%E4%B9%A0/Flink%E5%85%A5%E9%97%A8%E5%AD%A6%E4%B9%A0%E9%A6%96%E9%A1%B5.png" onerror="this.onerror=null;this.src='/blog/img/404.jpg'" alt="Flink入门学习"/></a><div class="content"><a class="title" href="/blog/2020/12/13/Flink%E5%85%A5%E9%97%A8%E5%AD%A6%E4%B9%A0/" title="Flink入门学习">Flink入门学习</a><time datetime="2020-12-13T10:21:57.000Z" title="发表于 2020-12-13 18:21:57">2020-12-13</time></div></div></div></div></div></div></div></main><footer id="footer" style="background-image: url(/blog/2021/01/29/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95/%E6%A1%86%E6%9E%B6%E5%A5%97%E8%B7%AF%E8%A7%A3%E7%AE%97%E6%B3%95%E9%A6%96%E9%A1%B5.jpg)"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2021 By Cai XianQuan</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">Hi,  welcome  to  my  <a  target="_blank" rel="noopener" href="https://www.caixianquan.tk">blog</a>!</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><div class="search-dialog__title" id="local-search-title">本地搜索</div><div id="local-input-panel"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div></div><hr/><div id="local-search-results"><div id="local-hits"></div><div id="local-stats"><div class="local-search-stats__hr" id="hr"><span>由</span> <a target="_blank" rel="noopener" href="https://github.com/wzpan/hexo-generator-search" style="color:#49B1F5;">hexo-generator-search</a>
 <span>提供支持</span></div></div></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js"></script><script src="/blog/js/utils.js"></script><script src="/blog/js/main.js"></script><script src="/blog/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/medium-zoom/dist/medium-zoom.min.js"></script><script src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><script src="/blog/js/search/local-search.js"></script><div class="js-pjax"><script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><script src="/js/bookmark.js"></script><script defer="defer" id="fluttering_ribbon" mobile="false" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-fluttering-ribbon.min.js"></script><script id="click-heart" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/click-heart.min.js" async="async" mobile="true"></script></div></body></html>